◀ Prev · Parts · Full · Next ▶

There is a constructive null cover of RANDc. This means that all effective tests for randomness (that is, constructive null covers) are, in a sense, subsumed by this universal test for randomness, since any sequence that passes this single test for randomness will pass all tests for randomness. (Martin-Löf 1966) Intuitively, this universal test for randomness says "If the sequence has increasingly long prefixes that can be increasingly well-compressed on this universal Turing machine", then it is not random." -- see next section.

Construction sketch: Enumerate the effective null covers as ( ( U m , n ) n ) m {\displaystyle ((U_{m,n})_{n})_{m}} . The enumeration is also effective (enumerated by a modified universal Turing machine). Now we have a universal effective null cover by diagonalization: ( ∪ ∪ n U n , n + k + 1 ) k {\displaystyle (\cup _{n}U_{n,n+k+1})_{k}} .

If a sequence fails an algorithmic randomness test, then it is algorithmically compressible. Conversely, if it is algorithmically compressible, then it fails an algorithmic randomness test.

Construction sketch: Suppose the sequence fails a randomness test, then it can be compressed by lexicographically enumerating all sequences that fails the test, then code for the location of the sequence in the list of all such sequences. This is called "enumerative source encoding".cite-ref-9[9]

Conversely, if the sequence is compressible, then by the pigeonhole principle, only a vanishingly small fraction of sequences are like that, so we can define a new test for randomness by "has a compression by this universal Turing machine". Incidentally, this is the universal test for randomness.

◀ Prev · Parts · Full · Next ▶